import java.util.*;

/**
 * 1282. 用户分组
 * https://leetcode-cn.com/problems/group-the-people-given-the-group-size-they-belong-to/
 */
public class Solutions_1282 {
    public static void main(String[] args) {
//        int[] groupSizes = {3, 3, 3, 3, 3, 1, 3};  // output: {{5}, {0, 1, 2}, {3, 4, 6}}
        int[] groupSizes = {2, 1, 3, 3, 3, 2};  // output: {{1}, {0, 5}, {2, 3, 4}}

        List<List<Integer>> result = groupThePeople(groupSizes);
        System.out.println(result);
    }

    /**
     * 题意分析：
     * groupSizes = {2, 1, 3, 3, 3, 2}
     * groupSizes[0] = 2：表示用户 0，所在的用户组大小为 2
     * groupSizes[1] = 1：表示用户 1，所在的用户组大小为 1
     * groupSizes[2] = 3：表示用户 2，所在的用户组大小为 3
     * 要求：把每个用户都分配到合适的用户组中（控制用户组大小不超过规定的大小）
     */
    public static List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> res = new ArrayList<>();
        // key：用户组大小，value：用户组用户 id（数组索引）
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < groupSizes.length; i++) {
            int size = groupSizes[i];
            if (!map.containsKey(size)) {
                map.put(size, new ArrayList<>());
            }
            List<Integer> list = map.get(size);
            list.add(i);
            if (list.size() == size) {
                // 用户组人数已满，添加结果集，重新建立一个用户组
//                res.add(new ArrayList<>(list));
//                list.clear();
                res.add(list);
                map.put(size, new ArrayList<>());
            }
        }
        return res;
    }
}
